package II;
/*
剑指 Offer 10- II. 青蛙跳台阶问题
解题思路：滚动数组思想，三个变量，前两个变量决定第三个变量。
1 2 3 5
 */
public class Offer10 {

  public static void main(String[] args) {
    System.out.println(new Offer10().numWays(4));
  }

  public int numWays(int n) {
    if (n <= 2){
      return n;
    }
    if (n == 0){
      return 1;
    }
    int a = 0,b = 1,r = 1;
    for (int i = 2;i <= n;++i){
      a = b;
      b = r;
      r = (a + b) % 1000000007;
    }
    return r;
  }
}
